#include <iostream>
#include <vector>
#include "calcAllSubsets.h"

using namespace std;

// Use integers as an example
void calcSubsetsRecur(int *array, 
                    size_t elem_num, 
                    size_t loc,
                    vector<vector<int> *> &sets_vec) {
    if (array == NULL || loc == elem_num) {
        return;
    }

    int elem = array[loc];
    size_t i, vec_size = sets_vec.size();

    // For each existing subset, add the current elem
    // and create a new subset
    for (i = 0; i < vec_size; i++) {
        vector<int> *new_vec = new vector<int>(*sets_vec[i]);
        new_vec->push_back(elem);
        sets_vec.push_back(new_vec);
    }

    calcSubsetsRecur(array, elem_num, loc + 1, sets_vec);
}

void calcAllSubsets(int *array, size_t elem_num) {
    vector<vector<int> *> sets_vec;

    // Create an empty subset
    vector<int> *sub_set = new vector<int>();
    sets_vec.push_back(sub_set);

    calcSubsetsRecur(array, elem_num, 0, sets_vec);

    // Print out all the subsets
    vector<vector<int> *>::iterator subset_it;
    vector<int>::iterator elem_it;

    for (subset_it = sets_vec.begin(); subset_it != sets_vec.end(); ++subset_it) {
        vector<int> *subset_ptr = *subset_it;
        if (subset_ptr->empty()) {
            cout << "Empty set" << endl;
        }
        else {
            for (elem_it = subset_ptr->begin(); elem_it != subset_ptr->end(); ++elem_it) {
                cout << *elem_it << "\t";
            }
            cout << endl;
        }

        // delete the subset
        delete subset_ptr;
    }

    sets_vec.clear();
}

